{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Count Number of Unival Subtrees\n",
    "\n",
    "[原题](https://mp.weixin.qq.com/s/VJUYYzhLd7DplBPW5J5g3A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "A unival tree is a tree where all the nodes have the same value. Given a binary tree, return the number of unival subtrees in the tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "The following tree should return `5`:\n",
    "\n",
    "```text\n",
    "  0\n",
    " / \\\n",
    "1   0\n",
    "   / \\\n",
    "  1   0\n",
    " / \\\n",
    "1   1\n",
    "```\n",
    "\n",
    "Those 5 trees are:\n",
    "\n",
    "- Three leaves with the value 1.\n",
    "- A leaf with the value 0.\n",
    "- A triangle subtree with 3 nodes at the bottom, all of their values are 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    ''' Class Definition '''\n",
    "    def __init__(self, value: int):\n",
    "        self.value = value\n",
    "        self.left: Node = None\n",
    "        self.right: Node = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_unival_subtrees(root: Node) -> tuple:\n",
    "    ''' Algorighm: Recursive Traversal '''\n",
    "    \n",
    "    # When a node is None, it must be a unival subtree.\n",
    "    # [0]: The value of root node.\n",
    "    # [1]: Is it a unival subtree?\n",
    "    # [2]: How many unival subtree in the current tree?\n",
    "    if root is None:\n",
    "        return (None, True, 0)\n",
    "    \n",
    "    # Check the value, unival or not and its count of both child.\n",
    "    left = count_unival_subtrees(root.left)\n",
    "    right = count_unival_subtrees(root.right)\n",
    "    \n",
    "    if (root.value == left[0] or left[0] is None) and left[1] and (root.value == right[0] or right[0] is None) and right[1]:\n",
    "        return (root.value, True, left[2] + right[2] + 1)\n",
    "    else:\n",
    "        return (root.value, False, left[2] + right[2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "''' Main Scripts '''\n",
    "a = Node(0)\n",
    "a.left = Node(1)\n",
    "a.right = Node(0)\n",
    "a.right.left = Node(1)\n",
    "a.right.right = Node(0)\n",
    "a.right.left.left = Node(1)\n",
    "a.right.left.right = Node(1)\n",
    "print(count_unival_subtrees(a))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
